package leetcode_题库;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/8/20 13:15
 */
public class _118_杨辉三角 {
    public static void main(String[] args) {
        System.err.println(generate(5));
    }

    public static List<List<Integer>> generate(int numRows) {
        //创建一个结果集合（选用Arraylist是因为占用内存小，线程安全，且最后需要遍历）
        List<List<Integer>> ret = new ArrayList<>(numRows);
        //遍历行
        for (int i = 0; i < numRows; i++) {
            //创建一个子集合，为“行”
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i){
                    //若这是一行的开头或末尾，就插入1，讨巧解决了第1、第二行的特殊行
                    row.add(1);
                    continue;
                }
                //不continue的话，就需要计算上一部分的值了，行数为i-1，列数分别是j-1和j，取二者和，插入即可
                row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
            }
            //将“行”插入到集合中
            ret.add(row);
        }
        return ret;
        /*

            > 2022/08/20 13:50:34
            解答成功:
                执行耗时:0 ms,击败了100.00% 的Java用户
                内存消耗:39.1 MB,击败了72.64% 的Java用户

         */
    }
}
